package edu.gatech.cs3240.DFA;

import java.util.ArrayList;

import edu.gatech.cs3240.NFA.NFA;
import edu.gatech.cs3240.NFA.State;
import edu.gatech.cs3240.NFA.Transition;
import edu.gatech.cs3240.NFA.NFA.IllegalNFAOperationException;


public class DFAGenerator {
	
		public static DFA convertNFAtoDFA(NFA nfa) {
		DFA dfa;
		State dfaStates;
				
			//Convert the start state to a DFA state 
			//(recursively converts it's subsequent states).
		dfa = new DFA(nfa.getStartState());
		//dfa.getStartState().setAccepting(false);
		
		dfa.setStartState(buildDFAstate(dfa.getStartState()));
		
		return dfa;
	}


	private static State buildDFAstate(State root) {
		
		ArrayList<Transition> transitions;
		State convertedDFAstate;
		
		/* get the closure on the 'root' state and then look at it's remaining
		 * transitions. (these will be consuming transitions)
		 */
		System.err.println(new NFA(root));
		System.err.println();
		
		convertedDFAstate = getEpsilonClosure(root);
		transitions = convertedDFAstate.getPaths();
		
		System.err.println(new NFA(convertedDFAstate));
		
			/*go through the remaining transitions and change the target state to the
			 * converted target state
			 */
	
		for(int i = 0; i < transitions.size(); i++){
			if(transitions.get(i).getTarget() != root){
					transitions.get(i).setTarget(buildDFAstate(transitions.get(i).getTarget()));
			} else
				transitions.get(i).setTarget(convertedDFAstate);
		}		
		return convertedDFAstate;		
	}
	
	private static boolean isDFAstate(State target) {
		ArrayList<Transition> transitions = target.getPaths();
		boolean isDFAstate = true;
		
		for(int i = 0; i < transitions.size(); i++){
			if (transitions.get(i).isEpsilon()){
				isDFAstate = false;
				break;
			}
		}
		return isDFAstate;
	}


	private static State getEpsilonClosure(State nfaState){
		return getEpsilonClosure(nfaState, new ArrayList<State>());
	}
	
	public static State getEpsilonClosure(State s, ArrayList<State> added) {
		State ns = new State(s.isAccepting());
		Transition t;
		added.add(s);
		// First collapse the epsilon transitions.
		for(int i = 0; i < s.getPaths().size(); i++) {
			t = s.getPaths().get(i);
			if(t.isEpsilon()) {
				if(!added.contains(t.getTarget())) {
					if(t.getTarget() != s){
						State temp = getEpsilonClosure(t.getTarget(), added);
						added.add(t.getTarget());
						collapse(ns, temp);
					}
				}
			}
		}
		
		// Now we can process the non-epsilon transitions.
		for(int i = 0; i < s.getPaths().size(); i++) {
			t = s.getPaths().get(i);
			if(added.contains(t.getTarget())) {
				// I'm looping back to a state I've already consumed.
				if(!t.isEpsilon()) {
					if(t.getTarget() == s)
						ns.addTransition(ns, t.getConsumable());
					else{
						ns.addTransition(t.getTarget(), t.getConsumable());
					}
				} // If it's an epsilon transition, ignore it.
				continue;
			}
			if(!t.isEpsilon()) {
				ns.addTransition(t.getTarget(), t.getConsumable());
			} else {
				added.add(t.getTarget());
				State temp = getEpsilonClosure(s.getPaths().get(i).getTarget(), 
						added);
				collapse(ns, temp);
			}
		}
		return ns;
	}	
	
	/**
	 * Add all the transitions from the second state to the first.
	 * @param first A state.
	 * @param second Another state.
	 */
	private static void collapse(State first, State second) {
		for(int i = 0; i < second.getPaths().size(); i++) {
			if(second.getPaths().get(i).getTarget() == second)
				first.addTransition(first,
						second.getPaths().get(i).getConsumable());
			else first.addTransition(second.getPaths().get(i).getTarget(),
					second.getPaths().get(i).getConsumable());
		}
		if(second.isAccepting())
			first.setAccepting(true);
	}
}
